#ifndef HASH_H
#define HASH_H
#include <iostream>
using std::cout;
using std::endl;


template < class Key, class Value > class htable {
public:
    class entry {
        friend class htable < Key, Value >;
        Key key;
        Value val;
        int hash;
        entry *next;
        entry *listcopy(entry * src) {
            if (src == 0)
                return 0;
            entry *ret = new entry(src->key, src->val, listcopy(src->next));
            return ret;
        }
    public:
        entry():key(), val(), hash(0), next(0) {
        }
        entry(const Key & k, const Value & v, entry * nxt = 0):key(k), val(v), hash(0), next(nxt) {
        }
        entry(const entry & x):key(x.key), val(x.val), hash(x.hash), next(x.next) {
        }
        entry & operator=(const entry & x) {
            if (this == &x)
                return *this;
            delete next;
            key = x.key;
            val = x.val;
            hash = x.hash;
            next = listcopy(x.next);
        }
        ~entry() {
            delete next;
        }
        Key getKey() {
            return key;
        }
        Value getValue() {
            return val;
        }
    };
private:
    entry * table;
    int capacity;
    int count;
    int threshold;
    float loadFactor;
    void rehash() {
        int oldCapacity = capacity;
        entry *oldTable = table;
        capacity = oldCapacity * 2 + 1;
        table = new entry[capacity];
        threshold = (int)(capacity * loadFactor);
        for (int i = oldCapacity; i-- > 0;) {
            for (entry * old = oldTable[i].next; old != 0; old = old->next) {
                entry *e = new entry(*old);
                int index = (e->hash & 0x7FFFFFFF) % capacity;
                e->next = table[index].next;
                table[index].next = e;
            }
        }
        delete[]oldTable;
    }
public:
    htable(int initial = 101, float load = 0.75):table(new entry[initial]), capacity(initial), count(0), threshold((int)(initial * load)), loadFactor(load) {
    }
    virtual ~ htable() {
        delete[]table;
    }
    htable(const htable & H) {
        capacity = H.capacity;
        count = H.count;
        threshold = H.threshold;
        loadFactor = H.loadFactor;
        table = new entry[capacity];
        for (int i = 0; i < capacity; i++) {
            table[i] = H.table[i];
        }
    }

    htable & operator=(const htable & H) {
        if (this == &H)
            return *this;
        delete[]table;
        capacity = H.capacity;
        count = H.count;
        threshold = H.threshold;
        loadFactor = H.loadFactor;
        table = new entry[capacity];
        for (int i = 0; i < capacity; i++) {
            table[i] = H.table[i];
        }
        return *this;
    }

    entry *get(const Key & k) const {
        entry *ret;
        int hash = hashfunc(k);
        int index = (hash & 0x7FFFFFFF) % capacity;
        for (ret = table[index].next; ret != 0; ret = ret->next) {
            if (k == ret->key)
                return ret;
        }
        return ret;
    }

    void put(const Key & k, const Value & v) {
        entry *e;
        int hash = hashfunc(k);
        int index = (hash & 0x7FFFFFFF) % capacity;
        for (e = table[index].next; e != 0; e = e->next) {
            if (k == e->key) {
                e->val = v;
                return;
            }
        }
        if (e == 0) {
            e = new entry(k, v, table[index].next);
            e->hash = hashfunc(k);
            table[index].next = e;
        }
        count++;
        if (count > threshold)
            rehash();
    }
    void dump() {
        for (int i = capacity; i-- > 0;) {
            for (entry * e = table[i].next; e != 0; e = e->next) {
                cout << e->getKey() << " -> " << e->getValue() << endl;
            }
        }
    }

    virtual int hashfunc(const Key &) const = 0;
};


#endif
